package com.aqie.easy.tree;

import com.aqie.easy.structure.TreeNode;

/**
 * 543 二叉树直径
 */
public class DiameterOfBinaryTree {
    // 全局变量 保留当前的最大二叉树直径
    private int res = 0;
    /**
     * 1, DFS 2ms
     * 以某个结点为根节点的子树的左右子树高度之和
     * @param root
     * @return
     */
    public int diameterOfBinaryTree(TreeNode root) {
        dfs(root);
        return res;
    }

    private int dfs(TreeNode root) {
        if (root == null) return 0;
        int r = dfs(root.right);
        int l = dfs(root.left);
        // 更新二叉树直径
        res = Math.max(res, l + r);
        // 返回该节点层数
        return Math.max(l, r) + 1;
    }
}
